package 剑指offer;

import java.util.Arrays;

/**
 * @author: tyy 剑指 Offer
 * 492. 构造矩形
    作为一位web开发者， 懂得怎样去规划一个页面的尺寸是很重要的。 现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求：
    1. 你设计的矩形页面必须等于给定的目标面积。
    2. 宽度 W 不应大于长度 L，换言之，要求 L >= W 。
    3. 长度 L 和宽度 W 之间的差距应当尽可能小。
    你需要按顺序输出你设计的页面的长度 L 和宽度 W。
    示例：
    输入: 4
    输出: [2, 2]
    解释: 目标面积是 4， 所有可能的构造方案有 [1,4], [2,2], [4,1]。
    但是根据要求2，[1,4] 不符合要求; 根据要求3，[2,2] 比 [4,1] 更能符合要求. 所以输出长度 L 为 2， 宽度 W 为 2。
    说明:
    给定的面积不大于 10,000,000 且为正整数。
    你设计的页面的长度和宽度必须都是正整数。
 * @create: 2021-10-21 17:40
 * @description:
 **/
public class Solution11 {
    public int[] constructRectangle(int area) {
        int width = (int) Math.sqrt(area);
        while (area % width != 0) {
            width--;
        }
        return new int[]{area / width, width};
    }
    public int[] constructRectangle2(int area) {
        int w = 1, // 宽
                h = area, // 长
                minus = area - w,
                min = Integer.MAX_VALUE;
        int[] res = new int[2]; // 宽和长度的数组
        while(w <= h) {
            minus = area - w;
            if(w * h == area && minus < min) {
                min = minus;
                res[0] = h;
                res[1] = w;
            } else if(w * h > area) {
                h--;
            } else {// w * h < area
                w++;
            }
        }
        return res;
    }
    public static void main(String[] args) {
        int num = 15;
        int[] ints = new Solution11().constructRectangle(num);
        System.out.println("ints = " + Arrays.toString(ints));
    }
}

/**
 * JAVA版——提供完整思路

 --------------------------------------------

 【变量说明】

 数组长度为 n ，最小操作次数为 k ，操作前数组的最小值为 min ，操作前数组的最大值为 max ，操作前数组的第二大值为 max2 ，操作前数组所有数和为 sum 。

 --------------------------------------------

 【思路分析】

 假设你可以无误执行完整个流程，这样可以搭建流程执行前后的桥梁。

 将操作流程前后的量进行分析，找到一个不变量，构成等式，进行求解。

 根据题意，每次操作将会使 n - 1 个元素增加 1 。由于你执行了 k 次，所以一共会使 sum 增加 k * (n - 1) 。即操作结束后数组的和为 sum + k * (n - 1) 。

 贪心部分：在整个流程的每次操作中，最小的那个值都会增加 1 。（贪心的证明在下个板块，建议最后看）

 由贪心可知，经过k 步后， min 变为了 min + k ，也意味着此时数组的每一项都变为了 min + k ，所以操作结束后数组的和为 n * (min + k) 。

 根据等量代换：

 sum + k * (n - 1) = n * (min + k)
 sum + k * n - k = n * min + n * k
 sum - k = n * min
 k = sum - n * min
 所以，最短操作次数为 k = sum - n * min 。

 先求和再减去长度n个最小值，不是相当于每一项减去最小值再求和吗？

 数学证明：（证明公式为latex代码，课根据需要转为公式查看）

 \sum_{i=0}^{i=n-1}{nums\left[ i \right]}-n\times \min =\sum_{i=0}^{i=n-1}{nums\left[ i \right]}-\sum_{i=0}^{i=n-1}{\min}=\sum_{i=0}^{i=n-1}{nums\left[ i \right] -\min}
 最终结论：k = SUM(nums[i] - min)

 --------------------------------------------

 【贪心证明】

 结论：在整个流程的每次操作中，最小的那个值都会增加 1 。

 证明过程：

 这个贪心可能不好理解，这里我们可以分成两个部分来理解：

 第一部分就是 max2 在追赶 max 的过程，设这个过程执行了 k' 次，在这 k' 次中，每次必然会使 max 的以外的元素增加 1 ，直到产生一个新的元素大于 max 为止（这个元素就是 max2 位置的元素，记为 max'），这个阶段 min 每次都增加了 1 ，并且这一步的前一步，max' 是等于max 的，之后的每一步都是 max' 和 max 争夺最大值的阶段， max' 和 max 轮流增加 1 ，其他元素每次的增加 1。由于其他元素的增速是大于 max' 和 max 的，所以很快会有个数大于 max' 和 max （也就是原数组的第三大的数，记为 max''），之后就是 max 和 max' 和 max'' 轮流作为最大值的过程。……

 第二部分就是第一个部分的临界阶段，也就是由于增速差除了原来最小的数 min 其他数轮流作为最大值时，这个时候 min 所在位置的数会以一种很快的速度增长直到他比最大值的数小 1为止（也就是支出现两种数为止），然后除了最大值的数，其他都增加 1 ，直到弥补和最小值之间的差为止。这个部分 min 也一直在增加。

 例题：这里以[1,2,3,4] 为例

 第一个部分：

 [2,3,4,4]：其余数都在追赶你索引为3的数，最小数从1增加为了2。

 [3,4,5,4]：索引为2的数超过了索引为3的数，最小数从2增加为了3。

 [4,5,5,5]：其余数都在追赶你索引为2的数，最小数从3增加为了4。（此时只有两种类型的数 4 和 5 ，且差值为 1 ，进入第二部分）

 第二部分

 [5,6,5,6]：索引为1的数超过了索引为2的数，最小数从4增加为了5。

 [6,6,6,7]：其余数都在追赶你索引为1的数，索引为3的数超过了索引为1的数，最小数从5增加为了6。

 [7,7,7,7]：其余数都在追赶你索引为3的数，最小数从6增加为了7。

 --------------------------------------------
 */
